It is often desirable to combine digital information from two sources based on some relationship between the information from the two sources. Because such operations are common, it is critical that they be performed in an efficient manner.
For the purpose of explanation, examples of the techniques described herein shall be given in the context of database systems. However, the techniques are not limited to such a context, and may be applied in any context in which digital information from one source is being combined with digital information from another source.
In the context of a database system, in a typical join operation, rows from one table are joined with rows from another table based on a join key. For example, assume that a database has an “emp” table with information about employees, and a “dept” table with information about departments. Each row in the emp table corresponds to a particular employee, and has a deptID column that stores the unique identifier of the department in which the employee works. On the other hand, each row in the dept table corresponds to a particular department, and includes a column that stores the deptID of the department represented by the row. A typical join operation may involve combining each row in the emp table with the row in the dept table that has a matching deptID value. In this example, deptID is what is referred to as the “join key” of the join operation.